package com.ting.test.algorithms.二叉树;

/**
 * 搜索二叉树概念:
 * 1. 二叉树的每一个子树都是搜索二叉树
 * 2. 左子树的最大值小于根节点
 * 3. 右子树最小值大于根节点
 * 利用递归的思想
 */
public class 判断是搜索二叉树 {
    public static void main(String[] args) {
        TreeNode head = new TreeNode(2);
        Info info = process(head);
        System.out.println(info.isBst);
    }

    private static Info process(TreeNode node) {
        //base case
        if (null == node) {
            return null;//空节点不好返回 直接给空
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int max = node.val;
        int min = node.val;

        // 最大值一定是左子树和右子树中的最大值
        if (null != leftInfo) {
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if (null != null) {
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }

        boolean isBST = true;
        //如果左子树不为空，但是不是搜索二叉树 fase
        if (null != leftInfo && !leftInfo.isBst) {
            isBST = false;
        }
        //如果右子树不为空，但是不是搜索二叉树 fase
        if (null != rightInfo && !rightInfo.isBst) {
            isBST = false;
        }

        //如果左子树不为空，最大值大于等于 根节点 false
        if (null != leftInfo && leftInfo.max >= node.val) {
            isBST = false;
        }

        //如果右子树不为空，最小值小于等于 根节点 false
        if (null != leftInfo && leftInfo.min <= node.val) {
            isBST = false;
        }
        return new Info(isBST, min, max);

    }


    static class Info {
        boolean isBst;
        int min;
        int max;

        public Info(boolean isBst, int min, int max) {
            this.isBst = isBst;
            this.min = min;
            this.max = max;
        }
    }

}
